class Solution {
public:
    string longestPalindrome(string s) {
        int sz = s.size();
        string result(1,s[0]);
        int ans = 0;
        vector<vector<bool>> dp(sz+1,vector<bool>(sz+1,false));
        for(int i=0;i<sz;i++){
            dp[i][i]=true;
        }
        for(int i=1;i<sz;i++){
            for(int j=0;j<i;j++){
                if(s[i]==s[j]){
                    if(i-j==1 || dp[j+1][i-1]){
                        dp[j][i]=true;
                        if(i-j+1>ans){
                            ans=i-j+1;
                            result=s.substr(j,i-j+1);
                        }
                    }
                }
            }
        }
        return result;
    }
};